package com.practice.binarysearch;

public class Sqrt {
	public int sqrt(int n) {
		return sqrt(n, 1, n);
	}
	
	private int sqrt(int n, int lower, int upper) {
		int mid = (lower + upper)/2;
		if (mid==lower) return mid;
		
		int t = mid * mid;
		if (t > n || t < 0) {
			return sqrt(n, lower, mid);
		}
		else {
			return sqrt(n, mid, upper);
		}
	}
}
